1. Field of the Invention
The invention relates to an assignment of a part domain of a whole domain which is divided into a plurality of part domains to one of a plurality of mobile units.
2. Description of the Related Art
A division of a whole domain into a plurality of part domains and subsequent assignment of one or a plurality of these part domains to mobile units is normally done when a plurality of mobile units jointly and coordinatedly process a large whole domain, for example when a hall is cleaned by a plurality of cleaning robots, as described in H. Endres, W. Feiten, and G. Lawitzky, Field Test of a Navigation System: Autonomous Cleaning in Supermarkets, Int. Conf. on Robotics and Automation (ICRA), 1998, pp. 1779-1781.
Different methods or approaches are used for dividing the whole domain and for assigning the part domains to the plurality of robots. A static approach or static method and a dynamic approach or dynamic method are used.
In the case of a static method, i.e. in the case of a static division and assignment, each mobile unit is permanently assigned a predetermined part domain of a whole domain before commencement of an activity which will be carried out jointly by the mobile units, wherein the assignment can no longer be changed during the activity.
Various such static methods, differing only in the manner in which the whole domain is divided into part domains, are known from Hert et al., “Polygon Area Decomposition for Multiple-Robot Workspace Division”, Special Issue of International Journal of Computational Geometry and Applications on Applied Computational Geometry, vol. 8, no. 4, 1998, pp. 437-466; Bast et al., “The Area Partitioning Problem”, Proceedings of the 12th Canadian Conference on Computational Geometry, 2000, pp. 163-171; Bern et al., “Linear-size Nonobtuse Triangulation of Polygons”, Discrete and Computational Geometry, vol. 14, 1995, pp. 411-428; Christou et al., “Optimal Equipartition of Rectangular Domains for Parallel Computation”, Journal of Global Optimization, vol. 8, January, 1996, pp. 15-34; I. T. Christou, “Distributed Genetic Algorithms for Partitioning Uniform Grids”, University of Wisconsin Madison, Dept. of Computer Sciences Technical Report MP-TR-96-09, 1996; Yackel et al., “Minimum Perimeter Domain Assignment”, Mathematical Programming, vol. 78, no. 2, August 1997, pp. 283-303.
Hert et al. and Bast et al. disclose the cutting up of a whole domain into n adjacent part domains of equal size, wherein each part domain must contain a specific point, i.e. a starting point of a robot which is responsible for the respective part domain. The static methods disclosed in Hert et al. and Bast et al. are mathematically correct, but the resulting part domains or areas to be processed by robots are often unusable in practice.
The static approach disclosed in Bern et al. therefore seeks and specifies equally sized part domains of a whole domain, wherein the part domains preferably contain no sharp angles and can therefore be processed more effectively by robots.
Conversely, the static methods disclosed in Christou et al., I. T. Christou and Yackel et al. specify part domains of a whole domain such that the part domains have a smallest possible diameter in each case and therefore normally also a small size. It is thereby intended that robots, each processing one of the part domains, encounter each other less frequently at a boundary of the part domain they are to process and therefore the danger of a collision is reduced.
A significant disadvantage of these known static methods, in particular due to the permanent assignment of part domains in these methods, is that such methods are extremely inflexible and cannot be dynamically adapted to new situations.
If one of a plurality of robots fails, for example, its work or its part domain to be processed is not taken over by one of the other robots. This part domain remains unprocessed in this case.
The dynamic method provides the opposite, i.e. a dynamic division and assignment of part domains. With this type of method, the part domains are first divided during an activity of the mobile units. The assignment of the part domains takes place in a plurality of time-staggered stages.
As a result of these dynamics, the part domains which are currently assigned to a mobile unit change dynamically during the activity of the mobile units. In this case, therefore, a work task is not permanently predefined for the mobile units, but is first dynamically adapted to environmental conditions and/or boundary conditions during the activity of the mobile units.
A disadvantage of the dynamic division and assignment of part domains is that the mobile units must remain in regular communication contact with each other, in order tell each other about notifications or changes. This communication is normally implemented by a global communication network via which the mobile units communicate with each other.
One such method, being at least partly dynamic, is disclosed in Hert et al., Multiple-Robots Motion Planning=Parallel Processing+Geometry, 2001. In the mixed-dynamic method disclosed in Hert et al., which method combines a static approach with a dynamic approach, a whole domain is divided into (n+1) part domains before the start of a processing activity by mobile units. n part domains are distributed among the mobile units in accordance with the static approach described above. The (n+1)th part domain is dynamically divided among the mobile units at the end of the processing activity.
However, since this mixed-dynamic method features mainly static method parts, it also exhibits the disadvantages of such static methods as described above.